Along with progress of scientific technology, the flow and quality of video data in transmission of video sequence become more and more important. A video sequence is composed of a series of images in a continuous time. Because the required storage space of a video sequence is very large, for a limited storage equipment or transmission bandwidth, it is expected that the required storage space of the video sequence can be reduced. The video sequence thus needs to be compressed. Therefore, the video compression technique is required. Video compression usually makes use of removing redundancy in video data to achieve the object of compression. Motion estimation is a compression technique used to remove temporal redundancy on the time axis.
The motion estimation describes how to find the most approximate block with the present processed one on two adjacent frames of time axis in a video sequence. The motion estimation generally makes use of search points reduction and pixel decimation to reduce computational complexity. Methods of search points reduction include famous fast algorithms like three steps search (TSS) algorithm, 2D log search algorithm, new three points search algorithm (NTSS algorithm), diamond search algorithm, and motion vector field adaptive search technology (MV_FAST algorithm), and predictive motion vector field adaptive search technology (PMV_FAST algorithm).
For adjacent pixels on the same frame, the brightness thereof ought to be very similar. Therefore, for pixels in a block, it is not necessary for every pixel to undergo computational criterion of difference value. This is because some pixels in a block may be noise so that if they are taken into account when calculating difference value between blocks, decision of motion estimation will be affected. For a uniform block, there will usually little difference for the brightness values between adjacent pixels usually. Therefore, when calculating difference value between blocks, it is not necessary for every pixel to undergo computational criterion of difference value. It is only necessary to pick some pixels sufficiently to represent the block for comparison.
Computational complexity for comparison of blocks can be reduced if the really representative pixels can be found. Therefore, a pixel decimation using similarity between pixels to reduce computational complexity of motion estimation is thus provided. For motion estimation in video compression, the pixel decimation can be generally divided into regular pixel decimation and adaptive pixel decimation. These two methods have their respective advantages and disadvantages. The regular pixel decimation (e.g., ¼ pixel decimation) makes use of fixed samples to reduce sampling rate. The embodiment is thus very simple and quick. It is not necessary to calculate which pixels are more representative for calculation of block difference value. However, the positions of selected pixels by reducing the sampling rate are fixed. When the brightness values in a block vary abruptly, the pixels selected by the regular pixel decimation may be not sufficiently representative for adjacent pixels, resulting in loss of important information and thus causing errors in decision of motion estimation.
The advantage of adaptive pixel decimation is that the samples for reducing sampling rate are variable. The adaptive pixel decimation will dynamically select which pixels for representing the whole block to perform calculation of block difference value according to variation of brightness values in the block. Accordingly, when the brightness values vary abruptly, motion estimation will select more pixels to keep sufficiently representative. When the brightness values vary little, motion estimation only selects less pixels to have sufficient representation for calculation of block difference value. Although this way of pixel decimation can avoid the disadvantage that every pixel in a block undergoes the criterion of difference value calculation, redundant time will be wasted in determining which pixels are sufficiently representative, hence increasing extra computational complexity and thus increasing some computational burden of motion estimation.
The present invention aims to propose a new pixel decimation method, which can sieve out sufficiently representative pixels and will not increase extra computational complexity, hence effectively resolving the above disadvantages.